package org.kk.array;

/**
 * 搜索旋转数组中的最小数
 * @author kk
 * @Date 2021/1/21
 */
public class MinNumber {
    public static void main(String[] args) {
        int[] nums = {9,8,7,6,5,1,2,3,4};
        int i = minInReversingList(nums);
        System.out.println(i);
    }
    /**
     * 解法一 二分查找(寻找变化点)
     * 时间复杂度 O(log n) 空间复杂度 O(1)
     */
    public static int minInReversingList(int[] arr){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0, right = arr.length -1, mid = 0;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if(arr[mid] < arr[right]){
                right = mid;
            }else if(arr[mid] > arr[right]){
                left = mid + 1;
            }else{
                right--;
            }
        }
        return arr[left];
    }
}
